package com.ztom.hard;

/**
 * 正则表达式匹配
 * <p>
 * https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
 *
 * @author ZhangTao
 */
public class Code01IsMatch {

    public boolean isMatch1(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();
        return process(str, pattern, str.length, pattern.length);
    }

    private boolean process(char[] s, char[] p, int sl, int pl) {
        // 都匹配到开头位置
        if (sl <= 0 && pl <= 0) {
            return true;
        }
        // 如果目标串没匹配完, 正则串长度不能为 0
        if (pl <= 0) {
            return false;
        }
        // 如果目标串匹配完, 正则串还有剩余, 那末尾必须 *
        // 且剩余部分符合 a*a*a*
        if (sl <= 0) {
            return p[pl - 1] == '*'
                    // 然后继续尝试剩余部分
                    && process(s, p, sl, pl - 2);
        }
        // 都不为空, 考察正则串最后一个字符
        if (p[pl - 1] == '*') {
            // p 最后一个是 *, 考察前一个字符是否匹配
            if (s[sl - 1] == p[pl - 2] || p[pl - 2] == '.') {
                // 匹配 0 次
                return process(s, p, sl, pl - 2)
                        // 匹配 1 次或多次
                        || process(s, p, sl - 1, pl);
            } else {
                // 只能匹配 0 次
                return process(s, p, sl, pl - 2);
            }
        } else {
            // 最后一个字符必须匹配, 或者是 .
            return (s[sl - 1] == p[pl - 1] || p[pl - 1] == '.')
                    // 然后继续尝试剩余部分
                    && process(s, p, sl - 1, pl - 1);
        }
    }


    public boolean isMatch(String str, String pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        int m = s.length;
        int n = p.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
//        // 第 0 列
//        for (int i = 1; i <= m; i++) {
//            dp[i][0] = false;
//        }
        // 第 0 行
        for (int pl = 1; pl <= n; pl++) {
            dp[0][pl] = p[pl - 1] == '*' && dp[0][pl - 2];
        }
        for (int sl = 1; sl <= m; sl++) {
            for (int pl = 1; pl <= n; pl++) {
                if (p[pl - 1] == '*') {
                    if (s[sl - 1] == p[pl - 2] || p[pl - 2] == '.') {
                        dp[sl][pl] = dp[sl][pl - 2] || dp[sl - 1][pl];
                    } else {
                        dp[sl][pl] = dp[sl][pl - 2];
                    }
                } else {
                    dp[sl][pl] = (s[sl - 1] == p[pl - 1] || p[pl - 1] == '.')
                            && dp[sl - 1][pl - 1];
                }
            }
        }

        return dp[m][n];
    }
}
